/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-23
 * Time: 21:21
 */
public class Solution {
    //DP
    public int numSquares(int n) {
        //dp[0]=0
        int[] dp=new int[n+1];
        //dp[i]=dp[i - 一个数的平方]+1 中的最小值,
        //因为一个数的平方有很多,所以这个最小值要挨着遍历才能确定
        for(int i=1;i<=n;i++){
            int min=Integer.MAX_VALUE;
            for(int j=1;j*j<=i;j++){
                min=Math.min(min,dp[i-j*j]+1);
            }
            dp[i]=min;
        }
        return dp[n];
    }
}